/**
 * BTree
 * https://www.geeksforgeeks.org/implementation-of-b-tree-in-c/
 * 
 */
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>

#define M 4 //树的度

struct BTreeNode{
    int num_keys;//当前节点的key的个数
    int keys[M-1];//保存键的数组
    struct BTreeNode* children[M];//子树
    bool is_leaf;//是否是叶子节点，叶子节点是内部节点，即图上的倒数第二层，他也是由关键字组成
};
/**
 * 创建新节点
 */
struct BTreeNode* createNode(bool is_leaf){
    struct BTreeNode *newNode=(struct BTreeNode*)malloc(sizeof(struct BTreeNode));
    if(newNode==NULL){
        perror("内存申请失败...");
        exit(EXIT_FAILURE);
    }
    newNode->num_keys=0;
    newNode->is_leaf=is_leaf;
    for(int i=0;i<M;i++){
        newNode->children[i]=NULL;
    }
    return newNode;
}
/**
 * 对一个key满了的节点进行切分
 */
void splitChild(struct BTreeNode* parent,int index){
    struct BTreeNode* child=parent->children[index];
    struct BTreeNode* newNode=createNode(child->is_leaf);

    newNode->num_keys=M/2-1;
    //将key和子树都移动到新节点里面去
    for(int i=0;i<M/2-1;i++){
        newNode->keys[i]=child->keys[i+M/2];
    }
    if(!child->is_leaf){
        for(int i=0;i<M/2;i++){
            newNode->children[i]=child->children[i+M/2];
        }
    }
    child->num_keys=M/2-1;
    //改变父亲的孩子，给新节点腾出空间
    for(int i=parent->num_keys;i>index;i--){
        parent->children[i+1]=parent->children[i];
    }
    parent->children[index+1]=newNode;
    //改变父亲的键，让孩子的键插入进来
    for(int i=parent->num_keys;i>=index;i--){
        parent->keys[i+1]=parent->keys[i];
    }
    parent->keys[index]=child->keys[M/2-1];
    parent->num_keys++;

}
/**
 * 给非满节点插入key
 */
void insertNonFull(struct BTreeNode*node,int key){
    int i=node->num_keys-1;//当前节点中最后一个key的下标
    if(node->is_leaf){//如果是叶子节点
    //有序插入
        while (i>=0&&node->keys[i]>key)
        {
            node->keys[i+1]=node->keys[i];
            i--;
        }
        node->keys[i+1]=key;
        node->num_keys++;
    }else{//非叶子节点
    //找到孩子，然后插入
        while (i>=0&&node->keys[i]>key){
            i--;  
        }
        i++;
        if(node->children[i]->num_keys==M-1){
            splitChild(node,i);//如果满了，就先划分孩子
            //决定两个孩子中的哪一个应该插入
            if(node->keys[i]<key){
                i++;
            }
        }
        //以孩子作为新的根，递归查找，直到有合适的才插入
        insertNonFull(node->children[i],key);
        
    }
}
/**
 * 将key插入到btree中,插入的节点都是叶节点，当叶子节点满了之后
 * 从中间断开成两部分，中间的值放到parent中，两个部分作为两个子节点
 * 如果parent也满了，这parent会往上生成一个新的parent将自己分成两半
 */
void insert(struct BTreeNode**root,int key){
    struct BTreeNode *node=*root;
    if(node==NULL){//如果为空树，就先创建
        *root=createNode(true);
        (*root)->keys[0]=key;
        (*root)->num_keys=1;
    }else{
        if(node->num_keys==M-1){//如果满了，就先划分，然后让root指向子树，就和之前的逻辑一样了
            struct BTreeNode *new_root=createNode(false);
            new_root->children[0]=node;
            splitChild(new_root,0);
            *root=new_root;
        }
        //此时的root永远是不满的
        insertNonFull(*root,key);
    }
}
/**
 * 遍历btree
 */
void traverse(struct BTreeNode* root){
    if(root!=NULL){
        int i;
        for(i=0;i<root->num_keys;i++){
            traverse(root->children[i]);
            printf("%d ",root->keys[i]);
        }
        traverse(root->children[i]);
    }
}

int main(void){
    struct BTreeNode *root=NULL;
    insert(&root,10);
    insert(&root,20);
    insert(&root,5);
    insert(&root,6);
    insert(&root,12);
    insert(&root,30);

    printf("顺序遍历btree：");
    traverse(root);
    printf("\n");
    return 0;
}